翻訳と辞書 Words near each other ・ Random waypoint model ・ Random White Dude Be Everywhere ・ Random wire antenna ・ Random! Cartoons ・ Random-access channel ・ Random-access machine ・ Random-access memory ・ Random-access stored-program machine ・ Random-access Turing machine ・ Random.org ・ Randomajestiq ・ Randominta ・ Randomization ・ Randomization function ・ Randomized algorithm ・ Randomized algorithms as zero-sum games ・ Randomized block design ・ Randomized controlled trial ・ Randomized experiment ・ Randomized Hough transform ・ Randomized meldable heap ・ Randomized response ・ Randomized rounding ・ Randomized weighted majority algorithm ・ Randomness ・ Randomness extractor ・ Randomness merger ・ Randomness tests ・ Random—Burin—St. George's ・ Randon Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Randomized algorithms as zero-sum games ： ウィキペディア英語版 Randomized algorithms as zero-sum games Randomized algorithms are algorithms that employ a degree of randomness as part of their logic. These algorithms can be used to give good average-case results (complexity-wise) to problems which are hard to solve deterministically, or display poor worst-case complexity. An algorithmic game theoretic approach can help explain why in the average case randomized algorithms may work better than deterministic algorithms. ==Formalizing the game== Consider a zero-sum game between player A, whose strategies are deterministic algorithms, and player B, who’s strategies are inputs for A’s algorithms. The cost of a strategy profile is the running time of A’s chosen algorithm on B’s chosen input. Therefore, player A tries to minimize the cost, and player B tries to maximize it. In the world of pure strategies, for every algorithm that A chooses, B may choose the most costly input – this is the worst-case scenario, and can be found using standard complexity analysis. But in the real world, inputs are normally not selected by an ‘evil opponent’ – rather, they come from some distribution over inputs. Since this is the case, if we allow the algorithms to also be drawn from some distribution, we may look at the game as one that allows mixed strategies. That is, each player chooses a distribution over its strategies. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Randomized algorithms as zero-sum games」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.